Computer systems generally provide a memory manager to assist computer programs in the dynamic allocation and deallocation of memory. When a computer program needs a block of memory, it requests the memory manager to allocate a block. The memory manager maintains a "heap" of memory from which it allocates the blocks. The memory manager tracks which blocks are currently allocated to the computer program and which blocks are currently available to be allocated. A memory manager typically tracks the currently available blocks using a free list that links together the available blocks. The blocks of the heap that are not on the free list are currently allocated to the computer program.
Some memory managers require that computer programs notify the memory manager when an allocated block is no longer needed by the computer program. Upon receiving the notification, the memory manager adds the block to the free list so that the block is then available to be reallocated. Other memory managers, however, do not require such notification. These other memory managers employ a garbage collection technique to identify which allocated blocks are no longer needed (e.g., accessible) by the computer program. The blocks of memory that are allocated but no longer needed are referred to as "garbage." Periodically, such other memory managers invoke garbage collectors to identify the blocks of memory that are garbage and to add the identified blocks to the free list. If the garbage blocks were not collected, then the garbage blocks of memory could not be reused, and the memory manager may quickly run out of memory available to allocate to the computer program.
Two well-known techniques for garbage collection are mark-and-sweep garbage collection and copying garbage collection. Mark-and-sweep garbage collector proceed with a mark phase and then a sweep phase. During the mark phase, mark-and-sweep garbage collectors mark all blocks of memory that are accessible by the computer program. Mark-and-sweep garbage collectors typically identify accessible blocks by identifying root references to blocks of memory, such as references on the stack or in a register. The mark-and-sweep garbage collectors "mark" the blocks pointed to by these root references and any blocks that are pointed to by a marked block. After all accessible blocks are marked, the mark-and-sweep garbage collectors then start the sweep phase. During the sweep phase, mark-and-sweep garbage collectors start at one end of the heap and checks each block. If a block is not marked, then mark-and-sweep garbage collectors add that block to a free list. When the sweep phase is complete, all inaccessible blocks that were allocated (i.e., garbage) are now on the free list and available to be reallocated to the computer program.
The other well-known garbage collection technique is copying garbage collection. Like mark-and-sweep garbage collectors, copying garbage collectors also identify accessible blocks by following root references and references within any accessible block. Copying garbage collectors copy all accessible blocks from an old area to a new area in memory and update references to point to the accessible blocks in the new area. Once all accessible blocks have been copied, then the old area, which previously contained both the accessible blocks and the inaccessible blocks, contains only blocks that are available to be allocated.
The mark-and-sweep and the copying garbage collection techniques have various advantages and disadvantages. For example, mark-and-sweep garbage collection generally occurs much faster than copying garbage collection. The copying of blocks and the updating references can be time consuming, while the adding of a garbage block to a free list is relatively fast. Mark-and-sweep garbage collection, however, results in memory with much more fragmentation than copying garbage collection. In particular, copying garbage collection typically results in a large block of available memory (e.g., the old space), whereas mark-and-sweep garbage collection typically results in small blocks of available memory separated by allocated memory. As a result, developers of memory managers need to balance these advantages and disadvantages when selecting a garbage collection technique.
Developers also need to determine the appropriate time at which to perform garbage collection. If garbage collection is performed too frequently, then a significant percentage of the computer resources is spent searching for garbage when there is actually a small amount of garbage. In contrast, if garbage collection is performed too infrequently, then a user may notice very significant delays during garbage collection, albeit delays that occur infrequently, because a large amount of garbage may have been generated during the delay. Developers, therefore, typically select a time period at which to perform garbage collection that is a compromise of these considerations.